1
ปัญหาการเรียงลำดับฮาร์ดแวร์
AI032Lesson 7
00:00

ในฮาร์ดแวร์ประสิทธิภาพสูง สปีดคือชีวิต ลองนึกภาพกราฟิกโพรเซสเซอร์ (GPU) ที่ทำงาน Z-buffering: มันต้องจัดเรียงค่าความลึกจำนวนหลายล้านค่าต่อวินาที เพื่อตัดสินว่าพิกเซลใดอยู่ข้างหน้า จากนั้นวิศวกรก็อาศัย ตัวเปรียบเทียบเลขจำนวนเต็มบวก, วงจรที่ออกแบบให้เรียบง่าย ประมวลผลบิตจากทางซ้ายไปขวา (MSB ถึง LSB) โดยไม่ต้องใช้ทรัพยากรในการคิดคำนวณใดๆ

ความล้มเหลวของระบบเลขสองส่วนประกอบ

ระบบเลขสองส่วนประกอบมาตรฐานล้มเหลวในการทดสอบสำหรับฮาร์ดแวร์ที่เรียบง่าย ด้วยเหตุผลที่ว่า บิตเครื่องหมาย (sign bit) เป็น 1 สำหรับจำนวนลบ และเป็น 0 สำหรับจำนวนบวก ทำให้ค่าเช่น -1 (111...) ดูเหมือนจะมากกว่า +1 (001...) ซึ่งสร้างความไม่ต่อเนื่อง ความไม่ต่อเนื่อง, ทำให้ฮาร์ดแวร์ต้องใช้ตรรกะแบบซับซ้อนและช้าลงในการตรวจสอบขนาดของค่า

แนวทางแก้ไขด้วยสมบัติการเพิ่มขึ้นอย่างต่อเนื่อง

เพื่อกลับมาใช้งานได้อย่างมีประสิทธิภาพ เราจะใช้ รหัสเกิน (Excess Encoding) (การแทนค่าเบื้องต้น) โดยการปรับช่วงค่าให้ค่าต่ำสุดกลายเป็น 000... และค่ามากสุดกลายเป็น 111...เราจะแน่ใจว่า รูปแบบบิตจะระบุค่าตัวเลขได้อย่างเฉพาะเจาะจง โดยที่ลำดับตามตัวอักษร (lexicographical order) ตรงกับลำดับเชิงตัวเลข ลำดับตามตัวอักษร โดยตรง

รูปที่ 7.1: การล้มเหลวของเลขสองส่วนประกอบรูปที่ 7.2: รหัสเกิน-3 ชนะค่าฐานสิบ | บิต-1 | 111 0 | 000กระโดดตรรกะ!ค่าฐานสิบ | บิต-3 | 000-2 | 001-1 | 010 0 | 011การเพิ่มขึ้นอย่างต่อเนื่อง

คุณสมบัตินี้ทำให้ตัวเปรียบเทียบฮาร์ดแวร์ที่เรียบง่ายสามารถประมวลผลข้อมูลทศนิยมที่ชาญฉลาดได้ทันที

main.py
TERMINALbash — 80x24
> Ready. Click "Run" to execute.
>